/**
 * 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
    给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

    示例 1:

    输入: 
    [[1,1,0],
    [1,1,0],
    [0,0,1]]
    输出: 2 
    说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
    第2个学生自己在一个朋友圈。所以返回2。
    示例 2:

    输入: 
    [[1,1,0],
    [1,1,1],
    [0,1,1]]
    输出: 1
    说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
    注意：

    N 在[1,200]的范围内。
    对于所有学生，有M[i][i] = 1。
    如果有M[i][j] = 1，则有M[j][i] = 1。
 */

/**
 * @param {number[][]} M
 * @return {number}
 */
var findCircleNum = function(M) {
  let res = [] // 存放朋友圈的数组
  for(let i = 0; i < M.length; i++) {
      for(let j = 0; j < M[0].length; j++) {
          if(M[i][j] === 1) {
            M[j][i] = 1
            if(i == j) {
              res.push([i])
            } else {
              res.push([i,j])
            }
          }
      }
  }
  return dfs(res).length;
  function dfs(arr) {
      for(let i = 0; i< arr.length-1; i ++){
        for(let j = i+1; j< arr.length; j++) {
          let cur = arr[i], item = arr[ j]
          if(intersection(cur, item)) {
            arr[j] = union(cur, item)
            arr.splice(i, 1)
            dfs(arr)
          } 
        }
      }
      return arr
  }
  // return result;
  // 判断两个数组是否有交集
  function intersection(arr1, arr2) {
    let _arr2Set = new Set(arr2);
    let intersectionRes = arr1.filter(item => _arr2Set.has(item));
    return intersectionRes.length
  }
  function union(arr1, arr2) {
    let union = Array.from(new Set([...arr1, ...arr2]));
    return union
  }
};

console.log(findCircleNum([[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]))
console.log(findCircleNum([[1,1,0],[1,1,0],[0,0,1]]))
console.log(findCircleNum([[1,1,0],[1,1,1],[0,1,1]]))


var findCircleNum = function (M) {
  const visited = Array.from({ length: M.length }).fill(0);
  let res = 0;
  for (let i = 0; i < visited.length; i++) {
    if (!visited[i]) {
      visited[i] = 1;
      dfs(i);
      res++;
    }
  }
  return res;

  function dfs(i) {
    for (let j = 0; j < M.length; j++) {
      if (i !== j && !visited[j] && M[i][j]) {
        visited[j] = 1;
        dfs(j);
      }
    }
  }
};